import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public static List<Integer> findSubstring(String s, String[] words) {
        int len = words[0].length();
        HashMap<String, Integer> hashW = new HashMap<>();
        for (String str : words) {
            hashW.put(str, hashW.getOrDefault(str, 0)+1);
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            int left = i;
            int right = i;
            HashMap<String, Integer> hashS = new HashMap<>();
            int count = 0; // 记录有效字符串的个数
            while (right+len <= s.length()) {
                // 先拿到[right,right+len]区间的字符
                String s1 = s.substring(right, right+len); // 此方法为左闭右开
                hashS.put(s1, hashS.getOrDefault(s1, 0)+1);
                // 有效字符串
                // s1一定存在于hashS中
                if (hashS.get(s1) <= hashW.getOrDefault(s1, 0)) {
                    count++;
                }
                // 检查窗口的大小
                if ((right-left+1) > words.length*len) {
                    // 先检查[left,left+len]是否为有效字符串
                    String s2 = s.substring(left, left+len);
                    // s2一定存在于hashS中
                    if (hashS.get(s2) <= hashW.getOrDefault(s2, 0)) {
                        count--;
                    }
                    // 对应的次数得减少
                    hashS.put(s2, hashS.getOrDefault(s2, 0)-1);
                    left += len;
                }
                if (count == words.length) {
                    list.add(left);
                }
                right += len;
            }
        }
        return list;
    }

    public static void main(String[] args) {
        String[] words = {"word","good","best","good"};
        List<Integer> list = findSubstring("wordgoodgoodgoodbestword", words);
        System.out.println(list);
    }
}